InforLorV4, Main, Exploration, bibRecord, 00BC23

Predicative functional recurrence and poly-space

Identifieur interne : 00BC23 ( Main/Exploration ); précédent : 00BC22; suivant : 00BC24

Predicative functional recurrence and poly-space

Auteurs : Daniel Leivant [États-Unis] ; Jean-Yves Marion [France]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:6A3159D9DEA2267255861D9784131F302B55D193

Descripteurs français

Pascal (Inist)
- Complexité calcul, Informatique théorique, Récurrence.

English descriptors

KwdEn :
- Computational complexity, Computer theory, Recurrence.

Abstract

Abstract: We formulate a notion of predicative function types, and define predicative recurrence over functions, both in equational style and as an applicative formalism, pointing out the equivalence between the two approaches. We then show that a function is poly-space iff it is defined using predicative functionals obtained by ramified recurrence over words.

Url:

https://api.istex.fr/ark:/67375/HCB-4ZBX2BXM-C/fulltext.pdf

DOI: 10.1007/BFb0030611

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Predicative functional recurrence and poly-space</title>
<author><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name>
</author>
<author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:6A3159D9DEA2267255861D9784131F302B55D193</idno>
<date when="1997" year="1997">1997</date>
<idno type="doi">10.1007/BFb0030611</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-4ZBX2BXM-C/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001872</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001872</idno>
<idno type="wicri:Area/Istex/Curation">001853</idno>
<idno type="wicri:Area/Istex/Checkpoint">002756</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002756</idno>
<idno type="wicri:doubleKey">0302-9743:1997:Leivant D:predicative:functional:recurrence</idno>
<idno type="wicri:Area/Main/Merge">00C401</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:97-0390458</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000C49</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000C30</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000C14</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C14</idno>
<idno type="wicri:doubleKey">0302-9743:1997:Leivant D:predicative:functional:recurrence</idno>
<idno type="wicri:Area/Main/Merge">00C511</idno>
<idno type="wicri:Area/Main/Curation">00BC23</idno>
<idno type="wicri:Area/Main/Exploration">00BC23</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Predicative functional recurrence and poly-space</title>
<author><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Departments of Computer Science, Indiana University, 47405, Bloomington, IN</wicri:regionArea>
<placeName><region type="state">Indiana</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>CRIN - CNRS & INRIA Lorraine, Université Nancy 2, B.P. 239, 54506, Vand∄uvre-lès-Nancy Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vand∄uvre-lès-Nancy</settlement>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<title level="s" type="abbrev">Lect Notes Comput Sci</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational complexity</term>
<term>Computer theory</term>
<term>Recurrence</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Complexité calcul</term>
<term>Informatique théorique</term>
<term>Récurrence</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We formulate a notion of predicative function types, and define predicative recurrence over functions, both in equational style and as an applicative formalism, pointing out the equivalence between the two approaches. We then show that a function is poly-space iff it is defined using predicative functionals obtained by ramified recurrence over words.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Grand Est</li>
<li>Indiana</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Vand∄uvre-lès-Nancy</li>
</settlement>
<orgName><li>Université Nancy 2</li>
</orgName>
</list>
<tree><country name="États-Unis"><region name="Indiana"><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name>
</region>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00BC23 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00BC23 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:6A3159D9DEA2267255861D9784131F302B55D193
   |texte=   Predicative functional recurrence and poly-space
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Predicative functional recurrence and poly-space

Predicative functional recurrence and poly-space

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.